<!DOCTYPE html>
<html>
	<head>
		<meta charset="utf-8" />
		<meta name="keywords" content="spring,Spring,java,web,程序员,博客,IT,技术,移动开发,Web前端,企业架构,编程语言,互联网,数据库,技术博客,blog,分布式架构,分布式">
		<meta name="description" content="cdcoder是一个程序员学习交流平台，深度IT技术博客，移动开发博客,Web前端博客,企业架构博客,编程语言博客,互联网博客,数据库博客,IT blog,核心关注IT知识传播，共享。为更好的IT产业贡献一份微薄的力量。">
		<link rel="shortcut icon" href="/img/code.ico" />
		<link rel="bookmark" href="/img/code.ico" />
		<title>算法与数据结构</title>
		<link href="../css/index.css" rel="stylesheet">
		<link href="../css/github.css" rel="stylesheet" />
		<style>
			body {
				font-size: 16px;
				font: 400 16px/1.62 Georgia, "Xin Gothic", "Hiragino Sans GB", "Droid Sans Fallback", "Microsoft YaHei", sans-serif;
				font-family: 'PT serif', 微軟正黑體, 微软雅黑, 华文细黑, Microsoft Yahei, Hiragino Sans GB, sans-serif;
				color: #D0CCCC;

				text-shadow: 0px 0px 1px rgba(24, 22, 22, 0.35);
				background-color: #000;
			}
				table {
				border:2;
				border-color:#F3F3F3; ;
			}
				p{ text-indent:2em; padding:0px; margin:0px; }
		</style>
	</head>
	<body>

		<header>
			<div class="logo"><a href="/index.html">徐思润博客</a></div>
			<nav>
				<ul id="starlist">
					<li><a href="/java/index.html">java</a></li>
					<li><a href="/data/index.html">算法与数据结构</a></li>
					<li><a href="/db/mysql.html">数据库</a></li>
					<li><a href="/distribution/index.html">分布式</a></li>
					<li><a href="/framework/index.html">架构</a></li>
					<li><a href="/interview/index.html">面试与被面试</a></li>
					<li><a href="/live/index.html">日常生活</a></li>
					<li><a href="/about.html">关于我</a></li>
					<li><a href="/baby/index.html">baby墙</a></li>
				</ul>
			</nav>
		</header>
		<div class="box">
			<h1 style="text-align: center;">Stack and Queue</h1>
			 
			<p>Java里有一个叫做<em>Stack</em>的类，却没有叫做<em>Queue</em>的类（它是个接口名字）。当需要使用栈时，Java已不推荐使用<em>Stack</em>，而是推荐使用更高效的<em>ArrayDeque</em>；既然<em>Queue</em>只是一个接口，当需要使用队列时也就首选<em>ArrayDeque</em>了（次选是<em>LinkedList</em>）。</p>
			<h1 data-breakpage>总体介绍</h1>
			<p>要讲栈和队列，首先要讲<em>Deque</em>接口。<em>Deque</em>的含义是“double ended queue”，即双端队列，它既可以当作栈使用，也可以当作队列使用。下表列出了<em>Deque</em>与<em>Queue</em>相对应的接口：</p>
			<figure>
				<table border="2"  >
					<thead>
						<tr>
							<th>Queue Method</th>
							<th>Equivalent Deque Method</th>
							<th>说明</th>
						</tr>
					</thead>
					<tbody>
						<tr>
							<td><code>add(e)</code></td>
							<td><code>addLast(e)</code></td>
							<td>向队尾插入元素，失败则抛出异常</td>
						</tr>
						<tr>
							<td><code>offer(e)</code></td>
							<td><code>offerLast(e)</code></td>
							<td>向队尾插入元素，失败则返回<code>false</code></td>
						</tr>
						<tr>
							<td><code>remove()</code></td>
							<td><code>removeFirst()</code></td>
							<td>获取并删除队首元素，失败则抛出异常</td>
						</tr>
						<tr>
							<td><code>poll()</code></td>
							<td><code>pollFirst()</code></td>
							<td>获取并删除队首元素，失败则返回<code>null</code></td>
						</tr>
						<tr>
							<td><code>element()</code></td>
							<td><code>getFirst()</code></td>
							<td>获取但不删除队首元素，失败则抛出异常</td>
						</tr>
						<tr>
							<td><code>peek()</code></td>
							<td><code>peekFirst()</code></td>
							<td>获取但不删除队首元素，失败则返回<code>null</code></td>
						</tr>
					</tbody>
				</table>
			</figure>
			<p>下表列出了<em>Deque</em>与<em>Stack</em>对应的接口：</p>
			<figure>
				<table  border="2" >
					<thead>
						<tr>
							<th>Stack Method</th>
							<th>Equivalent Deque Method</th>
							<th>说明</th>
						</tr>
					</thead>
					<tbody>
						<tr>
							<td><code>push(e)</code></td>
							<td><code>addFirst(e)</code></td>
							<td>向栈顶插入元素，失败则抛出异常</td>
						</tr>
						<tr>
							<td>无</td>
							<td><code>offerFirst(e)</code></td>
							<td>向栈顶插入元素，失败则返回<code>false</code></td>
						</tr>
						<tr>
							<td><code>pop()</code></td>
							<td><code>removeFirst()</code></td>
							<td>获取并删除栈顶元素，失败则抛出异常</td>
						</tr>
						<tr>
							<td>无</td>
							<td><code>pollFirst()</code></td>
							<td>获取并删除栈顶元素，失败则返回<code>null</code></td>
						</tr>
						<tr>
							<td><code>peek()</code></td>
							<td><code>peekFirst()</code></td>
							<td>获取但不删除栈顶元素，失败则抛出异常</td>
						</tr>
						<tr>
							<td>无</td>
							<td><code>peekFirst()</code></td>
							<td>获取但不删除栈顶元素，失败则返回<code>null</code></td>
						</tr>
					</tbody>
				</table>
			</figure>
			<p>上面两个表共定义了<em>Deque</em>的12个接口。添加，删除，取值都有两套接口，它们功能相同，区别是对失败情况的处理不同。<strong>一套接口遇到失败就会抛出异常，另一套遇到失败会返回特殊值（<code>false</code>或<code>null</code>）</strong>。除非某种实现对容量有限制，大多数情况下，添加操作是不会失败的。<strong>虽然<em>Deque</em>的接口有12个之多，但无非就是对容器的两端进行操作，或添加，或删除，或查看</strong>。明白了这一点讲解起来就会非常简单。</p>
			<p><em>ArrayDeque</em>和<em>LinkedList</em>是<em>Deque</em>的两个通用实现，由于官方更推荐使用<em>AarryDeque</em>用作栈和队列，加之上一篇已经讲解过<em>LinkedList</em>，本文将着重讲解<em>ArrayDeque</em>的具体实现。</p>
			<p>从名字可以看出<em>ArrayDeque</em>底层通过数组实现，为了满足可以同时在数组两端插入或删除元素的需求，该数组还必须是循环的，即<strong>循环数组（circular array）</strong>，也就是说数组的任何一点都可能被看作起点或者终点。<em>ArrayDeque</em>是非线程安全的（not
				thread-safe），当多个线程同时使用的时候，需要程序员手动同步；另外，该容器不允许放入<code>null</code>元素。</p>
			<p><img src='https://picabstract-preview-ftn.weiyun.com/ftn_pic_abs_v3/265cdae2222de9ae4c86733af2bc0b3aa0178f1d10b37c05d8e17a5d9d0eaf886df2f440e4d35559aee319a3c8ca4233?pictype=scale&from=30013&version=3.3.3.3&uin=182478932&fname=ArrayDeque_addLast.png&size=750' alt='ArrayDeque_base.png' referrerPolicy='no-referrer' /></p>
			<p>上图中我们看到，<strong><code>head</code>指向首端第一个有效元素，<code>tail</code>指向尾端第一个可以插入元素的空位</strong>。因为是循环数组，所以<code>head</code>不一定总等于0，<code>tail</code>也不一定总是比<code>head</code>大。</p>
			<h1 data-breakpage>方法剖析</h1>
			<h2>addFirst()</h2>
			<p><code>addFirst(E e)</code>的作用是在<em>Deque</em>的首端插入元素，也就是在<code>head</code>的前面插入元素，在空间足够且下标没有越界的情况下，只需要将<code>elements[<span
					 style='font-family:"Open Sans", "Clear Sans", "Helvetica Neue", Helvetica, Arial, sans-serif'>--</span>head] = e</code>即可。</p>
			<p><img   src='https://picabstract-preview-ftn.weiyun.com/ftn_pic_abs_v3/803dab1cec7a2104f205622ad5874c0903149daa67bd7572e9fbd883ed1ffbb11d231935a59005e5abc1c0edd210bd01?pictype=scale&from=30013&version=3.3.3.3&uin=182478932&fname=ArrayDeque_addFirst.png&size=750' referrerPolicy='no-referrer' /></p>
			<p>实际需要考虑：1.空间是否够用，以及2.下标是否越界的问题。上图中，如果<code>head</code>为<code>0</code>之后接着调用<code>addFirst()</code>，虽然空余空间还够用，但<code>head</code>为<code><span
					 style='font-family:"Open Sans", "Clear Sans", "Helvetica Neue", Helvetica, Arial, sans-serif'>-</span>1</code>，下标越界了。下列代码很好的解决了这两个问题。</p>
			<pre><code class='language-java' lang='java'>//addFirst(E e)
public void addFirst(E e) {
    if (e == null)//不允许放入null
        throw new NullPointerException();
    elements[head = (head - 1) &amp; (elements.length - 1)] = e;//2.下标是否越界
    if (head == tail)//1.空间是否够用
        doubleCapacity();//扩容
}
</code></pre>
			<p>上述代码我们看到，<strong>空间问题是在插入之后解决的</strong>，因为<code>tail</code>总是指向下一个可插入的空位，也就意味着<code>elements</code>数组至少有一个空位，所以插入元素的时候不用考虑空间问题。</p>
			<p>下标越界的处理解决起来非常简单，<code>head = (head <span style='font-family:"Open Sans", "Clear Sans", "Helvetica Neue", Helvetica, Arial, sans-serif'>-</span>
					1) &amp; (elements.length <span style='font-family:"Open Sans", "Clear Sans", "Helvetica Neue", Helvetica, Arial, sans-serif'>-</span>
					1)</code>就可以了，<strong>这段代码相当于取余，同时解决了<code>head</code>为负值的情况</strong>。因为<code>elements.length</code>必需是<code>2</code>的指数倍，<code>elements
					<span style='font-family:"Open Sans", "Clear Sans", "Helvetica Neue", Helvetica, Arial, sans-serif'>-</span> 1</code>就是二进制低位全<code>1</code>，跟<code>head
					<span style='font-family:"Open Sans", "Clear Sans", "Helvetica Neue", Helvetica, Arial, sans-serif'>-</span> 1</code>相与之后就起到了取模的作用，如果<code>head
					<span style='font-family:"Open Sans", "Clear Sans", "Helvetica Neue", Helvetica, Arial, sans-serif'>-</span> 1</code>为负数（其实只可能是-1），则相当于对其取相对于<code>elements.length</code>的补码。</p>
			<p>下面再说说扩容函数<code>doubleCapacity()</code>，其逻辑是申请一个更大的数组（原数组的两倍），然后将原数组复制过去。过程如下图所示：</p>
			<p><img  src='https://picabstract-preview-ftn.weiyun.com/ftn_pic_abs_v3/f6bfea5b98b11b72e3952d071ce2bdbf110631d879a7146852705d8e3b72cd0bb343713e7e00e4cafe4ea88caa323372?pictype=scale&from=30013&version=3.3.3.3&uin=182478932&fname=ArrayDeque_base.png&size=750' referrerPolicy='no-referrer' /></p>
			<p>图中我们看到，复制分两次进行，第一次复制<code>head</code>右边的元素，第二次复制<code>head</code>左边的元素。</p>
			<pre><code class='language-java' lang='java'>//doubleCapacity()
private void doubleCapacity() {
    assert head == tail;
    int p = head;
    int n = elements.length;
    int r = n - p; // head右边元素的个数
    int newCapacity = n &lt;&lt; 1;//原空间的2倍
    if (newCapacity &lt; 0)
        throw new IllegalStateException(&quot;Sorry, deque too big&quot;);
    Object[] a = new Object[newCapacity];
    System.arraycopy(elements, p, a, 0, r);//复制右半部分，对应上图中绿色部分
    System.arraycopy(elements, 0, a, r, p);//复制左半部分，对应上图中灰色部分
    elements = (E[])a;
    head = 0;
    tail = n;
}
</code></pre>
			<h2>addLast()</h2>
			<p><code>addLast(E e)</code>的作用是在<em>Deque</em>的尾端插入元素，也就是在<code>tail</code>的位置插入元素，由于<code>tail</code>总是指向下一个可以插入的空位，因此只需要<code>elements[tail]
					= e<span style='font-family:"Open Sans", "Clear Sans", "Helvetica Neue", Helvetica, Arial, sans-serif'>;</span></code>即可。插入完成后再检查空间，如果空间已经用光，则调用<code>doubleCapacity()</code>进行扩容。</p>
			<p><img   src='https://picabstract-preview-ftn.weiyun.com/ftn_pic_abs_v3/dc4ab1ad4faf5ec176cb61eb8e12b820d585d01b755efdc48f8ff17edaa1c78a133a68952521427a11d7c4147b654f3f?pictype=scale&from=30013&version=3.3.3.3&uin=182478932&fname=ArrayDeque_doubleCapacity.png&size=750' referrerPolicy='no-referrer' /></p>
			<pre><code class='language-java' lang='java'>public void addLast(E e) {
    if (e == null)//不允许放入null
        throw new NullPointerException();
    elements[tail] = e;//赋值
    if ( (tail = (tail + 1) &amp; (elements.length - 1)) == head)//下标越界处理
        doubleCapacity();//扩容
}
</code></pre>
			<p>下标越界处理方式<code>addFirt()</code>中已经讲过，不再赘述。</p>
			<h2>pollFirst()</h2>
			<p><code>pollFirst()</code>的作用是删除并返回<em>Deque</em>首端元素，也即是<code>head</code>位置处的元素。如果容器不空，只需要直接返回<code>elements[head]</code>即可，当然还需要处理下标的问题。由于<code>ArrayDeque</code>中不允许放入<code>null</code>，当<code>elements[head]
					== null</code>时，意味着容器为空。</p>
			<pre><code class='language-java' lang='java'>public E pollFirst() {
    E result = elements[head];
    if (result == null)//null值意味着deque为空
        return null;
    elements[h] = null;//let GC work
    head = (head + 1) &amp; (elements.length - 1);//下标越界处理
    return result;
}
</code></pre>
			<h2>pollLast()</h2>
			<p><code>pollLast()</code>的作用是删除并返回<em>Deque</em>尾端元素，也即是<code>tail</code>位置前面的那个元素。</p>
			<pre><code class='language-java' lang='java'>public E pollLast() {
    int t = (tail - 1) &amp; (elements.length - 1);//tail的上一个位置是最后一个元素
    E result = elements[t];
    if (result == null)//null值意味着deque为空
        return null;
    elements[t] = null;//let GC work
    tail = t;
    return result;
}
</code></pre>
			<h2>peekFirst()</h2>
			<p><code>peekFirst()</code>的作用是返回但不删除<em>Deque</em>首端元素，也即是<code>head</code>位置处的元素，直接返回<code>elements[head]</code>即可。</p>
			<pre><code class='language-java' lang='java'>public E peekFirst() {
    return elements[head]; // elements[head] is null if deque empty
}
</code></pre>
			<h2>peekLast()</h2>
			<p><code>peekLast()</code>的作用是返回但不删除<em>Deque</em>尾端元素，也即是<code>tail</code>位置前面的那个元素。</p>
			<pre><code class='language-java' lang='java'>public E peekLast() {
    return elements[(tail - 1) &amp; (elements.length - 1)];
}
</code></pre>

		</div>
		<footer>
			<p>Design by <a href="http://cdcoder.cn" target="_blank">徐思润个人博客</a> </p>
			<p>备案号：<a href="/">蜀ICP备15014105号-1</a></p>
				<script type="text/javascript" src="https://s96.cnzz.com/z_stat.php?id=1277229191&web_id=1277229191"></script>
		</footer>
		<script src="../js/rainbow.min.js"></script>
		<script src="../js/java_h.js"></script>
	</body>
</html>
